\section{Distributed algorithm in weak adaptive adversary model}

In this section, we propose a set of distributed algorithms, {\em
  useful token forwarding} shown in Algorithm \ref{alg:useful}, to
solve the $k$-token dissemination problem in the weak adaptive
adversary model. We prove Algorithm \ref{alg:useful} can solve the
$k$-token dissemination problem in $O(n\log n)$ rounds if (i) the
communication graphs provided by the adversary have bounded degrees,
and (ii) the dissemination process starts with the state where each
node $u$ has token $t_i$ with probability $1/2$ for all $i$, which is
referred as state $\cal C$.

\begin{algorithm}[ht!]
\caption{Useful token forwarding running on node $v$}
\label{alg:useful}
\begin{algorithmic}[1]

  %\REQUIRE Dynamic network $G$.
  %\ENSURE Nodes output $k$ tokens when they receive all.
  
  %\medskip

  \FOR{each round of communication}
  \FOR{each of $v$'s neighbors $u$}

  \STATE Either send $u$ a token which $u$ dosen't have yet, or
  receive a new token from $u$ which $v$ doesn't
  have. \label{alg.step:token}

  \ENDFOR

  %\IF{All $k$ tokens are received}
  %\PRINT All $k$ tokens
  %\ENDIF
  \ENDFOR
\end{algorithmic}
\end{algorithm}

We call a node bad if it misses more than $3\log n$ tokens. Otherwise
it is a good node. In a round of communication, if at least one of the
good nodes receives a useful token, then we say it is a good
round. Otherwise, it is a bad round. A set of nodes with the same set
of tokens is referred to as a group. A group of good nodes is a good
group. Otherwise, it's a bad group.

\begin{lemma}
\label{lem:bad.group.size}
In state $\cal C$, any group with more than $3\log n$ nodes is a good
group with probability at least $1-1/n^3$.
\end{lemma}
\begin{proof}
In state $\cal C$, let $l$ be the number of nodes in a group. Then
probability that a node in this group misses any $k$ tokens is
\[ {n \choose l} \cdot {n \choose k} \cdot \rb{\frac{1}{2}}^{l\cdot k} \le n^l \cdot n^k \cdot \rb{\frac{1}{2}}^{l\cdot k} = \frac{2^{(l+k)\log n}}{2^{lk}}\]
Set both $l$ and $k$ to $3\log n$. Then the probability can be upper bounded by,
\[\frac{2^{(3\log n + 3\log n)\log n}}{2^{(3\log n)(3\log n)}} = \frac{1}{n^{3\log n}} \le \frac{1}{n^3} \]
Thus, by the definition any group with more than $3\log n$ nodes is a
good group with probability at least $1 - 1/n^3$.
\end{proof}

\begin{lemma}
\label{lem:bad.group.prob}
Let $l$ be the number of nodes in a bad group, and $M$ be the number
of missing tokens of any node in this group. Then $\prob{M \ge
  n/l} \le \frac{1}{2^{n/3}}$.
\end{lemma}
\begin{proof}
Since this is a bad group, by Lemma \ref{lem:bad.group.size} we know
$l<3\log n$. This implies ${n \choose l} \le {n \choose 3\log n}$ and
${n \choose n/l} \le {n \choose n/3\log n}$.
\begin{eqnarray*}
\prob{M \ge \frac{n}{l}} &=& {n \choose l}\cdot {n \choose n/l} \cdot \rb{\frac{1}{2}}^{l\cdot \frac{n}{l}}
= {n \choose l}\cdot {n \choose n/l} \cdot \rb{\frac{1}{2}}^n \\
&\le& {n \choose 3\log n} \cdot {n \choose n/(3\log n)} \cdot \rb{\frac{1}{2}}^n
\le n^{3\log n} \cdot n^{\frac{n}{3\log n}} \cdot \rb{\frac{1}{2}}^n \\
&=& 2^{3\log^2 n} \cdot 2^{n/3} \cdot \frac{1}{2^n}
= 2^{3\log^2 n} \cdot \frac{1}{2^{2n/3}}
\le \frac{1}{2^{n/3}}
\end{eqnarray*}
\end{proof}

\begin{lemma}
\label{lem:bound.degree}
In each round of communication, let $m$ be the number of groups. If the
communication graph has bounded dgree $\Delta$, then the number of
useful token exchanges is at least $m/\Delta=\Omega(m)$.
\end{lemma}

\begin{theorem}
If the token dissemination process starts with state $\cal C$, and the
adversary always provides bounded degree graphs as communication
network, then Algorithm \ref{alg:useful} completes in $O(n\log n)$
rounds.
\end{theorem}
\begin{proof}
In the proof, we are going to show: (i) there are $O(n\log n)$ good
rounds; (ii) there are $O(n\log n)$ bad rounds. Thus, we prove the
theorem. The correctness of (i) is easy to see. There are at most $n$
good nodes over time, and each good node misses at most $3\log n$
tokens. Therefore, the number of good rounds is $O(n\log n)$. Now we
focus on (ii). In a bad round, let $n_i$ be the number of nodes in bad
group $i$. By Lemma \ref{lem:bad.group.prob}, the total number of
missing tokens of all bad nodes is $\sum_i n_i \cdot n/n_i \le mn$
with probability at least $1-m/2^{n/3}$, where $m$ is the number of
bad groups. And by Lemma \ref{lem:bound.degree}, we know the number of
useful token exchanges is $\Omega(k)$ in each round. Since it is a bad
round, all these useful token exchanges go to bad nodes. Let $k_1$ be
the number of bad groups in round $1$, and define $T_i$ to be the
number of rounds taken for the number of bad groups to become $k_1 -
2i$ for the first time. Then the total number of bad rounds is bounded
by
\[\sum_i T_i \le \sum_i 2n \cdot \frac{1}{\Omega(k_1 - 2i)} \le \sum_i 2n \cdot \frac{1}{\Omega(n - 2i)} = O(n\log n)\]
Thus, we complete the proof of this theorem.
\end{proof}
